⟸ pàgina anterior ⟸

Exercici 5 (Tasca 6).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE)

Classificació V: propietats de les funcions computables

Per a cadascun dels llenguatges L següents, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R} o L \notin \mathbf{RE} \cup \mathbf{coRE}.

1. \{p \mid \varphi_p \text{ és injectiva}\}
   
2. \{p \mid \varphi_p \text{ és total i injectiva}\} (resoldre aquest exercici de RACSO pot donar algunes pistes)
   
3. \{p \mid \varphi_p \text{ és sobrejectiva}\}
   
4. \{p \mid \varphi_p \text{ és total i sobrejectiva}\}
5. \{p \mid \varphi_p \text{ és creixent}\}
   
6. \{p \mid \varphi_p \text{ és total i creixent}\}
   
7. \{p \mid \varphi_p \text{ és estrictament decreixent}\}
   
8. \{p \mid \varphi_p \text{ és total i estrictament decreixent}\}
   
9. \{p \mid \forall y > p\ \varphi_y \text{ és bijectiva}\}
   
10. \{p \mid \forall y < p\ \varphi_y \text{ és bijectiva}\}
    
11. \{p \mid \exists y > p\ \varphi_y \text{ és bijectiva}\}
    
12. \{p \mid \exists y < p\ \varphi_y \text{ és bijectiva}\}